package _18_剑指OfferII;

import _18_剑指OfferII.datastrcute.ListNode;

import java.util.HashMap;
import java.util.Map;

public class _025_剑指OfferII链表中的两数相加 {

    // 也可以把容器换成栈, 效果是一样的
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        // 保存当前节点对于的上一个节点
        Map<ListNode, ListNode> l1Map = new HashMap<>();
        Map<ListNode, ListNode> l2Map = new HashMap<>();

        while (l1.next != null) {
            l1Map.put(l1.next, l1);
            l1 = l1.next;
        }

        while (l2.next != null) {
            l2Map.put(l2.next, l2);
            l2 = l2.next;
        }

        // 进位标识
        boolean carry = false;
        ListNode nextNode = null;
        while (l1 != null || l2 != null) {
            int total = (l1 == null? 0: l1.val) + (l2 == null? 0: l2.val) + (carry? 1: 0);
            ListNode newNode = new ListNode(total % 10);
            newNode.next = nextNode;
            nextNode = newNode;
            carry = total > 9;
            l1 = l1Map.get(l1);
            l2 = l2Map.get(l2);
        }
        if (carry) {
            ListNode newNode = new ListNode(1);
            newNode.next = nextNode;
            return newNode;
        }
        return nextNode;
    }


}
